Many cryptosystems, such as RSA, utilize modular exponentiation as a step in obscuring data. Specifically, to encrypt data, encoded data, a, is raised to a power of a public exponent, e, and modulo a value N: c=ae mod N. Decryption is later performed and includes raising the encrypted data to a power of a private exponent, d: a=cd mod N. Similar modular exponentiation may be used to create digital signatures, with the exception that the use of the private and public exponents is switched: the private exponent, d, is used to initially encipher the data and the public exponent, e, is used to verify the signature later.
Typically, the values chosen for the key 3-tuple <e, d, N> are very large. For example, RSA generally uses a key size of 1,024 to 4,096 bits. With such large values, a naïve algorithm would utilize an inordinate amount of processing time to calculate the modular exponentiations used by a given cryptosystem.